#include <iostream>
#include <vector>
#include <queue>
#include <stack>

using namespace std;

// 图的邻接矩阵表示
class Graph
{
private:
    int V;                         // 图中顶点的数量
    vector<vector<int>> adjMatrix; // 邻接矩阵

public:
    Graph(int vertices) : V(vertices)
    {
        // 初始化邻接矩阵为全0
        adjMatrix.resize(V, vector<int>(V, 0));
    }

    // 添加边
    void addEdge(int src, int dest)
    {
        adjMatrix[src][dest] = 1;
        adjMatrix[dest][src] = 1; // 无向图需要这一步
    }

    // 深度优先搜索（DFS）
    void DFS(int start)
    {
        vector<bool> visited(V, false);
        stack<int> stk;
        stk.push(start);

        while (!stk.empty())
        {
            int current = stk.top();
            stk.pop();

            if (!visited[current])
            {
                cout << current << " ";
                visited[current] = true;

                for (int i = 0; i < V; ++i)
                {
                    if (adjMatrix[current][i] && !visited[i])
                    {
                        stk.push(i);
                    }
                }
            }
        }
        cout << endl;
    }

    void DFS2(int start)
    {
        vector<bool> visited(V, false);
        stack<int> s;

        s.push(start);

        while (!s.empty())
        {
            int cur = s.top();
            s.pop();

            if (!visited[cur])
            {
                cout << cur << " ";
                visited[cur] = true;
            }

            for (int i = 0; i < V; i++)
            {
                if (adjMatrix[cur][i] && !visited[i])
                {
                    s.push(i);
                }
            }
        }
        cout << endl;
    }

    // 广度优先搜索（BFS）
    void BFS(int start)
    {
        vector<bool> visited(V, false);
        queue<int> q;
        q.push(start);
        visited[start] = true;

        while (!q.empty())
        {
            int current = q.front();
            q.pop();
            cout << current << " ";

            for (int i = 0; i < V; ++i)
            {
                if (adjMatrix[current][i] && !visited[i])
                {
                    q.push(i);
                    visited[i] = true;
                }
            }
        }
        cout << endl;
    }

    void BFS2(int start)
    {
    }
};

int main()
{
    Graph graph(6);

    // 添加边
    graph.addEdge(0, 1);
    graph.addEdge(0, 2);
    graph.addEdge(1, 3);
    graph.addEdge(2, 4);
    graph.addEdge(2, 5);

    cout << "DFS traversal starting from node 0: ";
    graph.DFS2(0);

    cout << "BFS traversal starting from node 0: ";
    graph.BFS(0);

    return 0;
}
